/**
 * 2017年1月4日
 */
package algorithm;

import java.util.Arrays;

class HNode{
	public String sym;
	public int val;
	public HNode left;
	public HNode right;
	
	public HNode(String sym,int val) {
		this.sym = sym;
		this.val = val;
	}
	
	public String toString(){
		return sym+":"+val;
	}
	public int hashCode(){
		return sym.hashCode();
	}
	public boolean equals(Object o){
		return this.hashCode() == o.hashCode();
	}
}

public class HuffmanCoding {
	

	
	public static void main(String[] args) {
		int vals[] = {45,13,12,16,9,5}; 
		String syms [] = {"a","b","c","d","e","f"};
		HNode []nodes = new HNode[syms.length];
		for(int i=0;i<nodes.length;i++){
			nodes[i] = new HNode(syms[i], vals[i]);
		}
		Arrays.asList(nodes).forEach(System.out::println);
		HNode root = huffmanCoding(nodes);
		coding(root,syms.length);
		
	}
	public static String[] coding(HNode root,int num){
		f(root,"");	
		return null;
	}
	private static void f(HNode node,String str){
		if(node.left==null && node.right==null){
			System.out.println(node.sym + " --> " + str);
		}
		if(node.left!=null){
			String strl = str+"0";
			f(node.left,strl);
		}
		if(node.right!=null){
			String strr = str+"1";
			f(node.right,strr);
		}
	}
	public static HNode huffmanCoding(HNode nodes[]){
		get(nodes);
		for(int i=0;i<nodes.length;i++){
			if(nodes[i]!=null){
				return (nodes[i]);
			}
		}
		return null;
	}
	
	private static void get(HNode nodes[]){
		int [] res = findSmallestTwoIndex(nodes);
		if(res[0]==-1 || res[1]==-1) return ;
		else{
			HNode root = new HNode("+", nodes[res[0]].val+nodes[res[1]].val);
			root.left = nodes[res[0]];
			root.right = nodes[res[1]];
			nodes[res[1]]= null;
			nodes[res[0]] = root;
			get(nodes);
		}
	
	}
	
	private static int [] findSmallestTwoIndex(HNode[] nodes){
		int min = -1;
		int val = Integer.MAX_VALUE;
		for(int i =0;i<nodes.length;i++){
			HNode n = nodes[i];
			if(n==null) continue;
			if(n.val<val){
				val = n.val;
				min = i;
			}
		}
		val = Integer.MAX_VALUE;
		int min2 =-1;
		for(int i=0;i<nodes.length;i++){
			HNode n = nodes[i];
			if(n==null) continue;
			if(n.val< val && i!=min){
				val = n.val;
				min2 = i;
			}
		}
		return new int[]{min,min2};
		
	}

}
